package myTree;

import java.util.ArrayList;

public class GetParents {
    static String ans;            //存放x结点的所有祖先结点

    public static String Ancestor1(MyBTree bt, char x) //返回x的祖先
    {
        ans = "";
        Ancestor11(bt.b, x);
        return ans;
    }

    private static boolean Ancestor11(BTNode<Character> t, Character x) {
        if (t == null) return false;
        if (t.lchild != null && t.lchild.data == x) {
            ans += t.data + " ";        //t结点是x结点的祖先
            return true;
        }
        if (t.rchild != null && t.rchild.data == x) {
            ans += t.data + " ";        //t结点是x结点的祖先
            return true;
        }
        if (Ancestor11(t.lchild, x) || Ancestor11(t.rchild, x)) {
            ans += t.data + " ";        //祖先的祖先是祖先
            return true;
        }
        return false;            //其他情况返回false
    }

    public static String Ancestor2(MyBTree bt, char x) //返回x的祖先
    {
        ArrayList<Character> path = new ArrayList<Character>();//存放路径
        ans = "";
        Ancestor21(bt.b, x, path);
        return ans;
    }

    private static void Ancestor21(BTNode<Character> t, Character x, ArrayList<Character> path) {
        if (t == null) return;
        path.add(t.data);
        if (t.data == x) {
            path.remove(path.size() - 1);    //删除x结点
            ans = path.toString();
            return;
        }
        Ancestor21(t.lchild, x, path);    //遍历左子树
        Ancestor21(t.rchild, x, path);    //遍历右子树
        path.remove(path.size() - 1);    //从path中删除t结点,回退
    }

    public static String Ancestor3(MyBTree bt, char x) //返回祖先
    {
        char[] path = new char[100];
        int d = -1;            //path[0..d]存放根到x结点的路径
        ans = "";
        Ancestor31(bt.b, x, path, d);
        return ans;
    }

    private static void Ancestor31(BTNode<Character> t, Character x, char[] path, int d) {
        if (t == null) return;
        d++;
        path[d] = t.data;
        if (t.data == x) {
            for (int i = 0; i < d; i++)    //将path[0..d-1]存放的ans中
                ans += String.valueOf(path[i]) + " ";
            return;
        }
        Ancestor31(t.lchild, x, path, d);    //遍历左子树
        Ancestor31(t.rchild, x, path, d);    //遍历右子树
    }


}



